package MyTree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TreeUtils {
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(root != null || !stack.isEmpty()){
            // 循环到最左孩子
            while(root != null){
                // ~~前序遍历，存入结果集合~~
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            // 弹出栈顶元素
            root = stack.pop();
            // 等于它的右孩子
            root = root.right;
        }
        return list;
    }

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(root!=null || !stack.isEmpty()){
            // 一直压入左孩子
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            // ~~中序遍历，存入结果集合~~
            list.add(root.val);
            // 等于右孩子，此后右孩子也会被压如栈中（满足条件 root!=null）
            root = root.right;
        }
        return list;
    }

    public static List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stackIn = new Stack<TreeNode>();
        Stack<Integer> stackOut = new Stack<Integer>();
        List<Integer> list = new ArrayList<Integer>();
        // 前序遍历：中左右     后序遍历：左右中        后序遍历反向：中右左
        while(root != null || !stackIn.isEmpty()){
            while(root != null){
                stackIn.push(root);
                // // ~~后序遍历，存入第二个辅助栈~~ 中右左
                stackOut.push(root.val);
                // 这里较模板做了改动，先遍历所有的右孩子
                root = root.right;
            }
            root = stackIn.pop();
            // 再遍历左孩子
            root = root.left;
        }
        // ~~后序遍历，将第二个辅助栈中的元素存入结果集合~~ 左右中
        while(!stackOut.isEmpty()){
            list.add(stackOut.pop());
        }
        return list;
    }




    public static void main(String[] args) {

    }
}
